class Solution {
public:
    //创建一个dp表，i位置表示到该位置所有子数组和的最大值
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n + 1, -0x3f3f3f3f);

        for (int i = 1; i < n + 1; i++)
            dp[i] = max(nums[i - 1], dp[i - 1] + nums[i - 1]);
            
        int ret = dp[1];
        for (int i = 2; i < n + 1; i++)
            if (dp[i] > ret)
                ret = dp[i];

        return ret;
    }
};